%!TEX program = xelatex
\documentclass[11pt,utf8]{article}
\usepackage[no-math,cm-default]{fontspec}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
%\usepackage{xeCJK}
\usepackage{verbatim}
\usepackage{indentfirst}
\usepackage{syntonly}
\usepackage{fancyhdr}
\usepackage[unicode=true, colorlinks, linkcolor=black, anchorcolor=black, citecolor=black, urlcolor=black]{hyperref}
\usepackage{graphicx}
\usepackage[top = 1.2in, bottom = 1.3in, left = 1.2in, right = 1.2in]{geometry}
\usepackage{xcolor}
\usepackage{paralist}
\usepackage{ulem}
\usepackage{titlesec}
\usepackage{zhspacing}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{supertabular}
\usepackage{soul}
\usepackage{listings}
\usepackage{caption}
\usepackage{algorithm}
\usepackage[hang]{subfigure}
\usepackage{algpseudocode}

\defaultfontfeatures{Mapping=tex-text}
\zhspacing
%\setromanfont{Times New Roman}
%\newfontfamily\zhfont[BoldFont=Adobe Heiti Std]{Adobe Song Std}
\setmonofont[Scale=1]{Courier New}
\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt
\renewcommand{\algorithmicrequire}{ \textbf{Input:}} %Use Input in the format of Algorithm  
\renewcommand{\algorithmicensure}{ \textbf{Output:}} %UseOutput in the format of Algorithm  

\begin{document}

\definecolor{hlcolor}{rgb}{0.9, 0.9, 0.9}
\sethlcolor{hlcolor}
\newcommand{\code}[1]{\texttt{\hl{#1}}}

\newcommand{\hlink}[1]{
	\footnote{\href{#1}{\textsl{\underline{#1}}}}
}
\newcommand{\myhlink}[1]{
	\textsl{\url{#1}}
}\renewenvironment{proof}{\noindent{\textbf{证明：}}}{\hfill $\square$ \vskip 4mm}
\renewcommand{\algorithmicrequire}{ \textbf{Input:}} %Use Input in the format of Algorithm  
\renewcommand{\algorithmicensure}{ \textbf{Output:}} %UseOutput in the format of Algorithm  

\newtheorem{conclusion*}{结论}
\newcommand{\conclusion}[1]{
	\begin{conclusion*}\textup{#1}\end{conclusion*}
}
\let\enumerate\compactenum
\let\endenumerate\endcompactenum
\let\itemize\compactitem
\let\enditemize\endcompactitem
\setlength{\pltopsep}{5pt}
\setlength{\parindent}{2em}
\setlength{\footskip}{30pt}
\setlength{\baselineskip}{1.3\baselineskip}
\renewcommand\arraystretch{1.2}

\lstset{language=C++,
	backgroundcolor=\color{hlcolor},
	extendedchars=false,
	basicstyle=\ttfamily,
	keywordstyle=\bfseries,
	commentstyle=\itshape\color{gray},
	escapeinside=`'}

\title{\fontsize{19pt}{\baselineskip}\textbf{OOP Team Project Report --- \\3D Placement Using the T-tree Formulation}}
\author{计52~林锦坤~刘明华~朱佳豪}
\date{}

\pagestyle{fancy}
\renewcommand{\sectionmark}[1]{\markright{\thesection.\ #1}}
\renewcommand{\subsectionmark}[1]{}
\fancyhead[L]{\small\slshape OOP Team Project Report}
\fancyhead[R]{\small\slshape\nouppercase{\rightmark}}
\fancypagestyle{plain}{\fancyhead{}\fancyfoot{}\renewcommand{\headrulewidth}{0pt}}

%\titleformat*{\section}{\fontsize{16pt}{\baselineskip}\bfseries}

\thispagestyle{plain}

\maketitle

%\setcounter{tocdepth}{1}
%\renewcommand{\contentsname}{\LARGE 目录}
\tableofcontents
\newpage
\pagenumbering{arabic}
\setcounter{section}{0}

\section{项目介绍}
在这次\texttt{team project}中，我们小组选择的是第三个项目：实现基于\texttt{T-tree}的立方体三维布局。在这个项目\footnote{项目地址：\myhlink{http://git.oschina.net/lazycal/Three-D-Placement}}中，我们有若干大小不一的立方体，希望求解出一个包围箱将所有立方体框住，并通过调整立方体的布局，来最小化包围箱的体积。我们通过实现论文\cite{TTREE}中提到的\texttt{T-tree}来表示立方体间的相互位置关系。但由于立方体的布局方案数达到了
$O(n!\frac{3^{3n}}{2^{2n}n^{1.5}})$级别\footnote{详细证明请参见原论文}。显然直接枚举所有放置方案，效率是非常低下的。于是我们通过使用模拟退火算法，来优化立方体的布局，试图求得近似解。在项目中，我们对原论文提供的算法进行了进一步的优化与改进，并对不同情况下算法的效率进行了比较。为了更好地展现出立方体的布局方案，我们还实现了一个图形化界面，对求得的方案进行了渲染，并能生动、形象地展示出立方体的布局过程。

\section{算法原理}

\subsection{T-tree}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.6\textwidth]{image/t-tree.png}
  \caption{T-tree}
\end{figure}

\texttt{T-tree}是论文中提到的一种立方体空间位置关系的表示方法。\texttt{T-tree}是一棵三叉树，每个节点对应一个立方体，而树上节点之间的关系则对应着立方体的位置关系。树上的一个节点最多有三个儿子，其中左儿子对应在\texttt{Z}轴正方向上最近的立方体；中间儿子对应在\texttt{Y}轴正方向上最近的立方体；右儿子对应在\texttt{X}轴正方向上最近的立方体。每一棵\texttt{T-tree}对应一种位置关系，通过变换树的形态和旋转立方体，我们能得到立方体的所有三维空间布局方式。在本项目中，我们需要实现\texttt{T-tree}的表示，对\texttt{T-tree}的变换以及通过\texttt{T-tree}求得对应布局方案和对应最小包围箱的体积。

\subsubsection{T-tree到Placement}
本节介绍将一棵将\texttt{T-tree}对应到一种合法\footnote{此处的合法指满足方块不相交的限制条件。}布局方案的方法。首先我们规定：方块的位置由8个顶点中最靠近原点的顶点坐标确定，方块的$length,width,height$对应于$x,y,z$分量的长度，且共有$N$个立方体。由于树的节点与立方体其实是一一对应的，下文将不再区分立方体与树的节点。

\textbf{算法基本思想}：按照$x$坐标分层，一层一层\textbf{独立}地按照树结构放置方块，即根据约束确定$y,z$坐标，而后再将所有层摆在一起，在满足方块不相交的条件下，尽量压缩，即$x$取得尽量小。

\textbf{算法具体流程}：对整棵树进行前序遍历，遍历过程中确定z坐标：按照定义，根节点的坐标为0。对于任意一个非根节点$u$，如果他是左孩子，则$u.z\leftarrow u.parent.z+u.parent.height$。遍历过程中，若碰到右孩子，则对树进行剖分，即将这条边断掉。

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.7\textwidth]{figures/decom.png}
  \caption{\label{fig:decom1} 一个剖分例子}
\end{figure}

遍历结束后，原树被剖分为若干个小二叉树。图\ref{fig:decom1}显示了一个剖分的例子。这边每棵二叉树即对应于按$x$坐标所分出的一层。我们按照每棵树的根节点的访问顺序来单独处理每棵树，即求其中每个节点的$y$坐标。注意我们只需要满足所有$y,z$的约束，对于$x$的约束要求将在后面考虑。

\subsubsection{确定节点的$y$坐标}
\begin{figure}[H]
  \centering
  \subfigure[对应于\ref{fig:decom1}中的a,b,c构成的二叉树]{
    \label{fig:placement:1}
    \includegraphics[width=0.3\textwidth]{figures/placement_1.png}
  }
  \subfigure[没有满足尽量压缩的条件]{
    \label{fig:placement:wrong}
    \includegraphics[width=0.3\textwidth]{figures/placement_wrong.png}
  }
  \subfigure[正确的摆放方案]{
    \label{fig:placement:right}
    \includegraphics[width=0.3\textwidth]{figures/placement_right.png}
  }
\caption{\label{fig:placement}摆放方案}
\end{figure}

所以我们将所有方块投影到$Z-Y$平面上。如图\ref{fig:placement:1}。问题变成平面上一些矩形，它们的$z$坐标已经确定，每个矩形只能左右移动，确定它们的位置，即$y(\geq 0)$坐标，使得它们满足\texttt{T-tree}的约束条件，并且尽量压缩，即每个矩形的y坐标都不能再减小。图\ref{fig:placement:wrong}显示了一种错误方案。图\ref{fig:placement:right}显示了一种正确摆放方案。

算法可以形象的如下描述：将此想象成一个不会有“消去”（即一行都有方块则移去此行）的俄罗斯方块游戏，重力方向为$Y$轴的负方向，$Z$轴为地面。我们按照前序遍历（注意此时是在剖分后的二叉树上遍历）的顺序，在无穷高的地方一个个“放下”矩形。最终的结果即为我们的摆放方案。

\begin{figure}[H]
  \centering
  \subfigure[插入矩形a]{
    \label{fig:contour:a}
    \includegraphics[width=0.4\textwidth]{figures/contour_a.png}
  }
  \subfigure[插入矩形b]{
    \label{fig:contour:b}
    \includegraphics[width=0.4\textwidth]{figures/contour_b.png}
  }
  \caption{\label{fig:contour} 插入矩形a或b}
\end{figure}


为了模拟这个“俄罗斯方块游戏”，我们用一个双向链表$contour$维护轮廓线（可以形象地理解为“从高处落到地面的一条细绳”，绳的拐点为$contour$的元素，顺序则按照拐点在绳上的先后顺序排列，如图\ref{fig:contour}，黄色线条即为轮廓线，拐点依次编号为$\cdots,A,B,C,\cdots$）：

初始加入$(0,-\infty)$，$(0,\infty)$。对于以后新加入的一个矩形$v$，\[v.y \leftarrow \max\{p.y | p \in contour \land p.z \in (v.z, v.z+v.height)\}\]如图\ref{fig:contour:b}，答案就是$D$和$E$中$y$的最大值。注意这里有个边界情况：$(v.z, v.z+v.height)$中没有点，对应于图\ref{fig:contour:a}的情况。此时$contour$中在区间前后的点（$E$和$F$）相邻，即连成一条与z轴平行的线，记这条线端点的$y$坐标为$y'$，则$v.y \leftarrow y'$。

之后将区间$[v.z, v.z+v.height]$中的端点删除。找到$[v.z, v.z+v.height]$的前一个点，记为$p_l$，后一个点为$p_r$（无论是矩形a还是b，前后的点都为E和F），在$p_r$前插入$(v.y + v.width, v.z)$，$(v.y + v.width, v.z + v.height)$，$(p_l.y, v.z)$，$(p_r.y, v.z + v.height)$。为了加速，每次我们都从上一次的$p_r$开始扫描。可以证明每个点只最多会被扫描到2次。因而此步骤复杂度为$O(N)$。

\subsubsection{确定方块的$x$坐标}
求完$y$坐标后，再将所有二叉树合并，此时再考虑$x$的约束。

算法可以形象的如下描述：仍然将此想象成一个不会有“消去”的俄罗斯方块游戏，不过是3维的，重力方向为$x$的负方向，$Z-Y$面为地面。我们按照访问顺序来单独处理每棵树，对树内每个方块从“高处放下”。算法流程如下：设当前块为$u$，之前块的集合为$S$，\[u.x \leftarrow \max\{w.x+w.length | \text{在}Z-Y\text{平面投影上}w\text{与}u\text{相交} \land w\in S\}\]\[S \leftarrow S+u\]
%这个步骤相当于求出在$Z-Y$平面投影上与当前方块有相交的方块w的\texttt{w.x+w.length}的最值。
可以直接暴力$O(N^2)$实现。项目中为了优化常数，增加了两个优化：

\begin{itemize}
\item \textbf{优化1} ：若没有访问过发生变换\footnote{参见\ref{Transform}}的节点，则不计算$x$，沿用上次计算的结果，因为此时$x$的值不会变。
\item \textbf{优化2} : 使用双向链表$cube\_list$按照$x$关键字维护每个方块。并记录每个方块在链表中的位置$end\_z$，以及第一个在$Z$轴投影上与当前方块相交的位置$start\_z$。
\end{itemize}

加了这两个优化，复杂度仍为$O(N^2)$，但实测速度已经提升许多。

算法分两步：\texttt{FindMaxX}与\texttt{InsertX}，下面是具体的伪代码：

\begin{algorithm}[H]
  \caption{FindMaxX($u$, $cube\_list$)}
  \label{isap}
  \begin{algorithmic}[1]
    \Require $u$: 当前节点（方块）;
    \If {$u$是树的根}
    \State $iter$ = $cube\_list$的第一个元素
    \Else
    \State $iter$ = $u.parent$.start\_z
    \EndIf
    \While {$iter$.z + $iter$.height $\leq u$.z}
        \State $++iter$ 
    \EndWhile \Comment{找到第一个在$Z$轴投影上与当前方块相交的位置start\_z}
    \State $u$.start\_z = $iter$
    \If {没有访问过产生变换的节点 $\land$ 上一次计算过方块的坐标} 
    \State \Return \Comment{优化1}
    \EndIf
    \While {$iter$.z < $u$.z+$u$.height}
    \If {$iter$和$u$相交}
    \State $u$.x = max($u$.x, $iter$.x)
    \EndIf
    \State $++iter$
    \EndWhile
  \end{algorithmic}
\end{algorithm}
\begin{algorithm}[H]
  \caption{InsertX($u$, $cube\_list$)}
  \label{isap}
  \begin{algorithmic}[1]
    \Require $u$: 当前节点（方块）;
    \If {$u$是树的根}
    \State $iter$ = $cube\_list$的第一个元素
    \Else
    \State $iter$ = $u.parent$.end\_z
    \EndIf
    \While {$iter$.z $\leq u$.z}
        \State $++iter$
    \EndWhile
    \State $cube\_list$.insert(iter, u)
    \State $u$.end\_z = $--iter$
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
  \caption{DetermineX($cube\_list$, $S$)}
  \label{isap}
  \begin{algorithmic}[1]
    \Require $S$: 二叉树集合;
    \ForAll{$B \in S$}
        \ForAll{$u \in B$}
        \State FindMaxX($u$, $cube\_list$)
        \EndFor
    \EndFor
    \ForAll{$B \in S$}
        \ForAll{$u \in B$}
        \State InsertX($u$, $cube\_list$)
        \EndFor
    \EndFor

  \end{algorithmic}
\end{algorithm}
\subsubsection{变换}
\label{Transform}
由于在模拟退火过程中我们需要通过已有方案生成新方案。为此\texttt{T-tree}提供了三种变换方式:
\begin{itemize}
\item{\textbf{交换两个立方体的位置}} 通过随机交换\texttt{T-Tree}上的两个节点实现。
\item{\textbf{对一个立方体进行旋转}} 通过随机选择一个立方体，交换其长宽高实现。
\item{\textbf{改变树的形态}} 通过随机将\texttt{T-Tree}的一棵子树移动到新的位置实现。
\end{itemize}


\subsection{模拟退火}
\subsubsection{退火过程}
玻尔兹曼分布律指出：在温度为$T$的平衡态下，任何系统的微观粒子在某一状态区间的粒子数与该状态区间粒子的能量$E$有关，而且与$e^{-\frac{E}{kT}}$成正比，其中$k>0$是玻尔兹曼常数。玻尔兹曼分布率是统计物理中适用于任何系统的一个基本定律，$e^{-\frac{E}{kT}}$就是玻尔兹曼因子。这个定律说明，在能量越大的状态区间内的粒子数越小，而且随着能量的增大，大小相等的状态区间的粒子数按指数规律急剧地减小。

玻尔兹曼分布律被用于分析固体的退火过程。当我们对一个固体进行加热时，粒子的热运动变得剧烈。随着温度的不断上升，粒子逐渐脱离开其平衡位置，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态，这就是固体的溶解过程。而退火过程则刚好相反，随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0时，系统的能量将趋于最小值。
\subsubsection{Metropolis准则}
如果以粒子的能量来表达固体所处的状态，在温度$T$下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。根据这一物理现象，Metropolis给出了从状态$i$转换为状态$j$的准则：

\begin{itemize}
  \item 如果$E(j)\leq E(i)$，则状态转换以$1$的概率被接受；
  \item 如果$E(j) > E(i)$，则状态转换以$e^{\frac{E(i) - E(j)}{kT}}$的概率被接受。
\end{itemize}

其中$E(i)$、$E(j)$分别表示在状态$i$、$j$下的能量，$T$是温度，$k$＞0是波尔兹曼常数。Metropolis准则表达了这样一种现象：在温度$T$下，系统处于某种状态，由于粒子的热运动，系统的状态发生微小的变化，并导致了系统能量的变化。如果这种变化使得系统的能量减少，则接受这种变化；如果变化使得系统的能量增加，则以一定的概率接受这种变化。在给定的温度$T$下，当进行足够多次的状态变化后，系统将达到热平衡。此时系统处于某个状态$i$的概率由符合玻尔兹曼分布律，即：
\begin{equation} \label{1} P_i(T) = \frac{e^{-E(i)/kT}}{Z_T}\end{equation}

其中$Z_T = \sum_{j \in S}e^{-E(j)/kT}$ 为归一化因子，$S$是所有可能状态的集合。

通过推导，我们不难得出如下结论：在温度趋近于无穷大时，系统处于无序的状态，以等概率落入各个状态。随着温度的缓慢下降，如果系统交换得足够充分，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减少，使得系统各状态能量的期望值随温度的下降单调下降。当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0，即系统最终将以概率1处于具有最小能量的一个状态。
\subsubsection{模拟退火算法}
受固体退火过程的启发，Kirkpatrick等人意识到组合优化问题与固体退火过程的类似性，将组合优化问题类比为固体的退火过程，提出了求解组合优化问题的模拟退火算法。具体来说用组合优化问题的一个解来类比物理系统中的一个状态；用解的指标函数来类比状态的能量；用最优解来类比能量的最低状态。

在求解组合优化问题时，首先给定一个比较大的$t$值，这相当于给定一个比较高的温度$T$。随机给定一个问题的解$i$，作为问题的初始解。在给定的$t$下，随机产生一个问题的解$j$，$j\in N(i)$，其中N(i)是$i$的邻域。从解$i$到新解$j$的转移概率，则按照Metropolis准则确定，即：

\begin{align}
P_t(i \to j)= 
\left\{
\begin{aligned}
&1                            &       &f(j) < f(i) \\
&e^{-\frac{f(j)-f(i)}{t}}     &       &f(j) \geq f(i) \\
\end{aligned}
\right.
\end{align}
          
如果新解$j$被接受，则以解$j$代替解$i$，否则继续保持解$i$。重复该过程，直到在该控制参数$t$下达到平衡。与退火过程中的温度$T$缓慢下降相对应，每次达到平衡后，我们控制参数$t$缓慢下降，并重复前面的过程，直到控制参数$t$趋近于0为止。由我们前面的推导可知，此时我们得到的一定是该组合优化问题的一个最优解。

但从前面的推导可知，为了得到最优解，我们必须满足以下三个条件：
\begin{itemize}
	\item 初始温度足够高；
	\item 在每个温度下，状态的交换足够充分；
	\item 温度T的下降足够缓慢。
\end{itemize}

然而这样的条件与我们希望的低复杂度算法是相违背的。但在实际问题中，我们通常可以根据实际情况对条件进行弱化，从而得到令我们满意的问题较优解。

由此我们可以得到模拟退火算法的一份伪代码：

\begin{algorithm}
\caption{模拟退火算法}
\begin{algorithmic}[1]
\State 求出初始温度$T_0$
\State 随机生成一个解$now$，计算其指标函数$f(now)$。
\While{未达到结束条件}
\While{在当前温度内未达到平衡}
\State 对当前解$now$进行随机变换，得到新解$new$，并计算其指标函数$f(new)$。
\If{$f(new)<f(now)$} \State $now=new$
\Else \State 根据Metropolis准则计算接受概$P(now \to new)$
\If{$P(now \to new) > Random(0, 1)$} \State now = new
\EndIf
\EndIf
\EndWhile
\State 降低温度
\EndWhile

  \end{algorithmic}
\end{algorithm}

在本项目中，问题的一个解即为一种布局方案，指标函数即为该布局方案对应的包围框的最小体积。结束条件为在一定次数内方案的指标函数未发生变化，此时说明解已收敛。而其他参数的选择以及生成新解的方式，将在后面进一步介绍。由于运行时间有限，温度下降的速度可能较快，每一个温度下的交换次数较少，从而导致一次模拟退火算法容易陷入局部较优解，而得不到全局最优解。故在本项目中，我们通过缩短一次模拟退火的时间，增加模拟退火过程的次数，从而保证解的质量更加稳定。

\subsubsection{生成新解的方式}
在模拟退火过程中，我们通过已有方案随机生成新方案。生成的新方案不应变化太大，应尽可能保留原有方案的优点。但同时也要要求能够通过生成新方案覆盖原问题的所有情况。对于这道题，我们共设计了三种生成新解的方式:
\begin{itemize}
\item{\textbf{交换两个立方体的位置}} 通过随机交换\texttt{T-Tree}上的两个节点实现。
\item{\textbf{对一个立方体进行旋转}} 通过随机选择一个立方体，交换其长宽高实现。
\item{\textbf{改变树的形态}} 通过随机将\texttt{T-Tree}的一棵子树移动到新的位置实现。
\end{itemize}

通过这三种操作，我们可以保证每一种布局方式所对应的解都能被覆盖。而对于这三种操作的出现概率，则与其对应的变化情况数成正比，从而保证每一组解随机到的概率都是相同的。在原论文中，因为实际背景的原因，立方体还有位置关系的限制，需要对于变换后不合法的情况进行处理，但在这里我们无需考虑。

\subsubsection{参数的选择}
前面提到为了得到组合优化问题的最优解，我们需要满足三个条件，然而这些条件与我们希望的低复杂度算法是相违背的。在实际问题中，我们通常需要根据实际情况对条件进行弱化，从而得到令我们满意的较优解。
\begin{itemize}
\item{\textbf{初始温度}}   一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率$P_0$近似等于1。在Metropolis准则下，即要求：
\begin{align} e^{-\frac{\Delta f(i,j)}{t_0}} \approx 1 \label{5}\end{align}

反解式\ref{5}，我们可以得到：$t_0 =\frac {\Delta f(i,j)}{ln(P_0^{-1})}$，其中$\Delta f(i,j) = max(f(i)- f(j))$。在这个问题中，我们取$P_0$为一个较大的值；并通过随机得到若干解，估计出指标函数的变化范围，从而得到初始温度。

\item{\textbf{交换次数}}    在每一个温度下，我们都要进行足够多次数的交换，以达到该温度下的平衡，但交换次数又直接与运行时间成正比。在本项目中，设置了两种运行模式，在时间限制小于十分钟时，我们在每个温度下进行$O(10^6 / n)$次交换（其中$n$表示立方体的数量），从而在较快时间内得到一个较优解；而当时间较充裕时，我们则根据时间限制，增加交换次数，从而追求更优秀的解。

\item{\textbf{温度下降方式}} 退火过程要求温度下降足够缓慢，常用的一种降温方法为等梯度下降。即通过设置衰减系数$\alpha$，使得温度每次按比率下降：$t_{k+1}=\alpha t_k$。在本项目中，我们根据温度所处的范围不同，设置了三个不同的下降速度，使得在温度较高时下降较快，温度较低时下降较慢，从而缩短问题收敛时间，提高解的质量。不难推出，衰减系数$\alpha$越小，温度下降越快，问题收敛所需时间也就越短，但我们得到解的质量却会受到影响。所以我们要在降温速度和解的质量之间寻找平衡点。同样的在本项目中设置了两组衰减系数，在时间限制小于十分钟时，我们的温度下降较快，从而在较快时间内得到一个较优解；而当时间较充裕时，我们则减缓温度下降速度，从而追求更优秀的解。

\end{itemize}

\section{图形化展示}

  \begin{figure}[h]
        \centering
        \includegraphics[height=0.6\textwidth]{image/Demo.png}
    	\caption{Demo}
  \end{figure}

    本项目的图形化界面，通过分解整个打包过程，致力于能够全面而清晰地展示解的空间布局。实现方面使用了\texttt{C++}语言，基于\texttt{OpenGL}库的代码编写，并借助了动画手段来演示算法部分所搜到的解，有以下几个特点:
    \begin{itemize}
        \item \textbf{视线宽阔} 轻松一览全局
        \item \textbf{模式丰富} 从不同角度剖析，更加自由的用户体验
        \item \textbf{操作简便} 单快捷键配合鼠标，减轻用户学习负担
        \item \textbf{界面优美} 精心挑选百种颜色，方块鲜明可辨
        \item \textbf{动画流畅} 使得学术性问题有了一定的演出效果
    \end{itemize}

\section{项目架构}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.8\textwidth]{image/uml.jpg}
  \caption{UML}
\end{figure}
\subsection{Cube}
\texttt{Cube}是项目中表示立方体的一个公共类，包含了立方体的长宽高和位置信息，并提供了一些通用接口。
\begin{itemize}
\item{构造函数}\\
\texttt{Cube}提供了三种构造函数，包括指定长宽高和体积等方式。
\item{\code{int GetVolume();}}\\
计算并返回立方体的体积。
\item{\code{void SetPos (int \_x, int \_y, int \_z);}}\\
设置立方体的位置。
\item{\code{void rotate();}}\\
通过交换长宽高，完成对立方体的旋转。
\item{\code{bool intersect\_y\_z(const Cube \&o);}}\\
判断两个立方体是否在\texttt{Y-Z}平面相交。
\item{\code{bool intersect(const Cube \&o);}}\\
判断两个立方体是否相交。
\item{\code{bool operator < (const Cube \& o);}}\\
根据立方体的位置，确定偏序关系。
\end{itemize}

\subsection{common}
类似stl的方法实现了栈和双向链表，功能与\texttt{STL}的\texttt{stack}和\texttt{list}类似，但是内存是在构造时事先分配好的，因而速度会稍快。若要增大内存，需要调用里面提供的\code{void resize(int \_n);}函数。
\subsubsection{\texttt{ListNode \&\& ListNode2}}
二元组和三元组
\subsubsection{\texttt{template<class T> List}}
List提供和\code{std::list}相同的操作：
\begin{itemize}
\item \code{push\_back(const T \&t);}
\item \code{insert(LIterator<T> iter, const T \&t);}
\item \code{erase(LIterator<T> iter);}
\item \code{void clear();}
\item \code{LIterator<T> begin();}\\返回尾指针对应的迭代器
\item \code{LIterator<T> end();}\\返回空指针对应的迭代器
\end{itemize}
不同的是用之前必须先声明List的长度不会超过\_n：\code{void resize(int \_n);}。具体操作方式可以参见\texttt{common\_unittest.cpp}文件。
\subsubsection{\texttt{template<class T> ListItem}}
List中的项，存有用户数据\code{T data}和两个指针\code{ListItem<T> *pre,*nxt}指向前一个和后一个，用于实现双向链表。
\subsubsection{\texttt{template<class T> LIterator}}
List的迭代器。
\subsubsection{\texttt{template<class T> Stack}}
提供与\code{std::stack}相同的操作。不同的是用之前必须先声明Stack的长度不会超过\_n：\code{void resize(int \_n);}。具体用法可以参见\texttt{common\_unittest.cpp}文件。
\subsection{T-tree}
\subsubsection{Node}
一个结构体，表示\texttt{T-tree}上的节点。有\code{parent, left\_child, middle\_child, right\_child, cube\_cid}几个属性。
\begin{itemize}
\item \code{int\& operator[](int index);}\\返回第i个成员变量。顺序如上所示，从0开始。
\end{itemize}
\subsubsection{TTree}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{figures/28.png}
  \caption{\label{fig:dot} n=28}
\end{figure}
存有\code{std::vector<Node> nodes\_;}，\code{std::vector<Cube> cubes\_;}等成员变量。注：其中有许多静态成员变量，这主要是为了加速操作。因为事实上一些中间临时变量（例如\code{contour}）是可以多个\texttt{TTree}一起使用的。
\\\textbf{public:}
\begin{itemize}
\item \code{TTree(std::vector<Cube> \&\_cubes);}\\由传进来的方块随机构造一棵\texttt{T-tree}。
\item \code{void GetPlacement(std::vector<Cube> \&res);}\\将放置方案放在res里，每个方块的\texttt{x,y,z}坐标已确定。
\item \code{int GetVolume();}\\返回体积。注意体积先前已经算过，故此函数复杂度为$O(1)$。
\item \code{void SwapNode(int u, int v);void MoveNode(int u, int v);void ModifyCube(int u, int k);}\\三种变换。
\end{itemize}
\textbf{private:}
\begin{itemize}
\item \code{void PrintTree();}\\将树结构用dot语言打印出来。若要看树的图形化展示，可以安装\href{http://www.graphviz.org/}{graphviz}来将dot文件可视化\ref{fig:dot}。\texttt{./data/}目录下也有几个示例。
\item \code{void TreePacking();}\\计算放置方案。
\item \code{bool CheckValid();}\\检查树的合法性。
\item \code{void Generate();}\\随机生成一棵树。
\item \code{void TreeDecomposition(int u);}\\剖分成多个二叉树。
\item \code{void PlaceModule(int u);}\\计算方块的$x,y,z$。
\item \code{void FindMaxY(int u);}\\计算方块的$y$坐标。
\item \code{void FindMaxX(int u);}\\计算方块的$x$坐标。
\item \code{void InsertX(int u);}\\将方块插入到$cube\_list\_$中。
\item \code{void ComputeVolume();}\\所有方块的$x,y,z$坐标都已确定。此函数计算出包裹这些方块的最小立方体的体积。
\end{itemize}

\subsection{模拟退火}


在项目的架构中，共有两个与模拟退火算法相关的类。
\subsubsection{Simulated\_Annealing}
\texttt{Simulated\_Annealing}是一个抽象类，其中包含有模拟退火算法的各项参数。调用前需要通过对其进行继承，并对两个虚函数\code{int Transform(TTree \& tree, std::vector<int> \& t);}和\code{void GetAns(std::vector<Cube> \&cubes);}进行完善。
\begin{itemize}
\item{\code{void SASolve();}}\\
包含了模拟退火算法的基本框架。
\item{\code{int Transform(TTree \& tree, std::vector<int> \& t);}}\\
回调函数，用户可以定义自己的生成新解方式，传入参数可用于辅助确定新解的生成，返回值用来告知基类变换的类型。
\item{\code{void GetAns(std::vector<Cube> \&cubes);}}\\
用于用户自定义问题的求解模式。
\end{itemize}

之所以将\texttt{Simulated\_Annealing}设计成抽象类，是为了实现多态和代码复用，得到更多实现方式的模拟退火算法。

\subsubsection{SA\_Solver}
\texttt{SA\_Solver}是一个继承类，对基类的两个虚函数进行了完善。

\begin{itemize}
\item{构造函数}\\
对于模拟退火过程的参数进行了设定;
\item{\code{void SetTimeLimitation(int time\_limitation);}}\\
用于设定运行时间限制。
\item{\code{void GetAns(std::vector<Cube> \&cubes);}}\\
通过在时间限制内不断调用基类的\code{void SASolve();}来对问题进行求解。
\item{\code{int Transform(TTree \& tree, std::vector<int> \& t);}}\\
定义了三种不同的变换，通过一定的策略随机选择一种变换，供基类调用。
\end{itemize}
\subsection{图形化展示}
\subsubsection{draw}
图形化展示的实现，运用了\textbf{单件}的OOP编程思想，将所有的图形化显示的架构封装在\texttt{Draw}类中。
\begin{itemize}
    \item \code{void init();}\\
        实现界面的初始化，直接进入全景模式。
    \item \code{void DrawAllCubes();}\\
        在已设定视角和透视关系的状态下，按顺序画出所有的方块，不会更新缓冲区。
    \item \code{void DrawDisplayCubes();}\\
        在已设定视角和透视关系的状态下，按顺序画出所有在展示中的方块，不会更新缓冲区，在展示模式下可用。
    \item \code{void DrawCube(const dCube \& c, dVec color);}\\
        在已设定视角和透视关系的状态下，画出某一个方块c，配色方案为color，不会更新缓冲区。
    \item \code{void DrawFrame();}\\
        在已设定视角和透视关系的状态下，以一定的透明度画出框架，配色方案为白色，不会更新缓冲区。
        调用完毕后，在更新缓冲区前不建议直接添加更多的方块，容易造成透视错误。
    \item \code{void FlyCube(const dCube \& c, dVec color);}\\
        使一个方块，沿x方向，从一定距离出插入到给定位置，配色方案为color，自动更新并缓冲区。
    \item \code{void CalcViewpoint();}\\
        通过视角柱坐标系下的坐标，计算得到对应的空间直角坐标系下的坐标，用于视角设定。
    \item \code{void SetViewpoint();}\\
        设定视角。
    \item \code{void RefreshSight();}\\
        刷新当前视角下的物体。
    \item \code{void Redisplay(bool refresh = true);}\\
        根据当前存储的状态，重新设定视角。 若refresh为true则会刷新所有物体，并更新缓冲区。
    \item \code{void BeginActionMode();}\\
        进入展示模式。
    \item \code{void StopActionMode();}\\
        退出展示模式，进入全景模式。
    \item \code{bool PlaceNext();}\\
        放置下一个方块，若操作成功返回true，否则返回false。 在展示模式下可用。
    \item \code{bool PlacePrevious();}\\
        退回到上一个方块。 若操作成功返回true，否则返回false。 在展示模式下可用
    \item \code{bool ActionMode();}\\
        返回是否处于展示模式。
    \item \code{void ProcessMove(int x, int y);}\\
        用于处理用鼠标拖动视角的函数。
    \item \code{double Radius();}\\
        得到视角与z轴应保持的距离。
    \item \code{void SetCylinderPos(double R, double theta, double z);}\\
        设定视角在柱坐标系下的坐标
    \item \code{void SetMousePos(int x, int y);}\\
        设定鼠标的当前位置。
    \item \code{void SetLeftButtonDown();}\\ 
        设定鼠标左键的按下状态。
    \item \code{void SetRightButtonUp();}\\
        设定鼠标右键的抬起状态。
    \item \code{void SetLeftButtonUp();}\\
        设定鼠标左键的按下状态。
    \item \code{bool LeftButtonDown();}\\
        返回当前鼠标左键是否按下。
    \item \code{void SwitchFrameFlag();}\\
        开关框架的显示状态。
    \item \code{static Draw* Instance();}\\
        返回Draw类的唯一实例的地址。
    \item \code{void Main(int \& argc, char ** argv);}\\
        Draw类的主函数，调用则打开图形化界面。
    \item \code{void LoadCubes(const std::string \& File\_Name);}\\
        从文件名为\texttt{File\_Name}的文件中读取所有方块及其对应位置。
    \item \code{void LoadCubes(const std::vector<Cube> \& cubes);}\\
        记录给定的方块列表，并初始化配色方案。
    \item \code{static void keyboard(unsigned char key, int x, int y);}\\
        OpenGL的键盘反馈函数。
    \item \code{static void mouse(int button, int State, int x, int y);}\\
        OpenGL的鼠标反馈函数。
    \item \code{static void display();}\\
        OpenGL的展示反馈函数。
    \item \code{static void reshape(int w, int h);}\\
        OpenGL的重置界面尺寸反馈函数。
    \item \code{static void mousemove(int x,int y);}\\
        OpenGL的鼠标移动反馈函数。
\end{itemize}
\subsubsection{辅助类}
除此之外，Draw类中还定义了两个辅助类
\begin{itemize}
    \item \texttt{dVec}类\\
        \texttt{double}类型的三元组，也可以认为是三维欧式空间的向量。
    \item \texttt{dCube}类\\
        \texttt{double}类型坐标边长的\texttt{Cube}类，用于存放空间中的方块。 写有各种形式的构造函数，并且有$<$运算符的定义。
\end{itemize}
\subsubsection{用户接口}
Draw类提供了三种用户接口
    \begin{itemize}
        \item \code{void Main(int \& argc, char ** argv);}
        \item \code{void LoadCubes(const std::string \& File\_Name);}
        \item \code{void LoadCubes(const std::vector<Cube> \& cubes);}
    \end{itemize}
    具体功能与用法如前文所述。\\
    其中\texttt{Loadcubes}函数用于初始化Draw类，\texttt{Main}函数则用于启动Draw类。

\subsection{用户接口}

\subsubsection{placement\_solver}
\texttt{placement\_solver}是一个与用户进行交互，通过调用\texttt{SA\_Solver}来求解三维布局问题的类。
\begin{itemize}
\item{\code{void LoadCube(const std::vector<Cube> \&);}}\\
 用于从\texttt{vector}读入立方体，并进行数据合法性检验;
\item{\code{void LoadCube(const std::string \&);}}\\
 用于从文件读入立方体，并进行数据合法性检验;
\item{\code{void LoadCube();}}\\
 用于从标准输入输出读入立方体，并进行数据合法性检验;
\item{\code{void Solve();}}\\
 用于求解放置方案;
\item{\code{void GetCube(std::vector<Cube> \& data);}}\\
 用于获取求得的布局方案;
\item{\code{void Output(std::string File\_Name);}} \\
用于输出求得的解，其中输出文件默认为\texttt{Output.txt}。
\end{itemize}
\subsubsection{test}
\texttt{test.cpp}中完成了对项目的测试，并通过命令行参数设置了不同的测试模式。
\begin{itemize}
\item{\code{void Cube\_Generater(vector<Cube> \&cubes, int n, int size);}}\\
 随机生成若干大小不一的立方体。
\item{\code{void Test\_Generater();}}\\
 随机生成测试数据。
\item{\code{void Draw(const vector<Cube> \& cubes, int argc, char *argv[]);}}\\
 在问题求解后，对方案进行图形化展示。
\item{\code{void Draw(const string \& File\_Name, int argc, char *argv[]);}}\\
 将输出文件中的方案进行图形化展示。
\item{\code{void Solve(vector<Cube> \& cubes);}} \\
调用\texttt{placement\_solver}对问题进行求解，并返回求得的方案。
\item{\code{bool check(vector<Cube> \& cubes);}} \\
检验求得的方案是否合法。
\item{\code{void Test();}}\\
 进行测试。
\end{itemize}

\subsubsection{batch\_test}
\texttt{batch\_test.cpp}中通过调用系统命令行，实现了一个简单地批量测试。

\section{编译与运行}
\subsection{编译}
项目提供了\texttt{makefile}文件，并添加了\texttt{-O2}的编译优化命令。由于图形化界面使用了\texttt{OpenGL}库，用户需事先安装\texttt{GLUT}等相关库文件。
\subsection{运行}
编译完成后，用户通过运行\texttt{main.exe}运行本项目，并可通过命令行参数来选择不同的测试模式。
\begin{itemize}
\item{\textbf{-LF INPUT\_FILE}} 用于指定输入文件名，默认输入文件名为\texttt{input.txt};
\item{\textbf{-SF OUTPUT\_FILE}} 用于指定输出文件名，默认输出文件名为\texttt{output.txt};
\item{\textbf{-D}} 表示在对问题求解完成后，对求得结果进行图形化展示;
\item{\textbf{-T num}} 用于指定运行时间。其中$num$为大于0的整数，表示运行的秒数，默认情况下$num = 600$。指定运行时间后，程序将在$num + 60$秒内结束。当运行时间较短时，程序将选择快速模式，在较短的时间内求得较优的解；当时间较充裕时，项目将选择精确计算模式，试图求得更优的解;
\item{\textbf{-DO}} 表示不对问题进行求解，而是对已有的输出文件中的方案进行展示，需通过同时使用\texttt{-SF}指定输出文件名，否则将默认从\texttt{output.txt}中读入方案。

\end{itemize}

\subsection{图形化界面使用}
在图形化界面中定义了两种模式：\textbf{全景模式}和\textbf{展示模式}。


\begin{figure}[h]
    \centering
    \subfigure[初始界面] {
        \includegraphics[width=0.45\textwidth]{image/Full_View.jpg}
    }
    \hspace{0.05\textwidth}
    \subfigure[带框架] {
        \includegraphics[width=0.45\textwidth]{image/Full_View_Framed.jpg}
    }
    \caption{全景模式}
\end{figure}

\begin{figure}[h]
    \centering
    \subfigure[方块1] {
        \includegraphics[width=0.25\textwidth]{image/Display_Mode_1.jpg}
    }
    \hspace{0.05\textwidth}
    \subfigure[方块2] {
        \includegraphics[width=0.25\textwidth]{image/Display_Mode_2.jpg}
    }
    \hspace{0.05\textwidth}
    \subfigure[方块3] {
        \includegraphics[width=0.25\textwidth]{image/Display_Mode_3.jpg}
    }
    \caption{展示模式}
\end{figure}

\begin{figure}[h]
    \centering
    \subfigure[] {
        \includegraphics[width=0.22\textwidth]{image/Action_1.jpg}
    }
    \hspace{0.0001\textwidth}
    \subfigure[] {
        \includegraphics[width=0.22\textwidth]{image/Action_2.jpg}
    }
    \hspace{0.0001\textwidth}
    \subfigure[] {
        \includegraphics[width=0.22\textwidth]{image/Action_3.jpg}
    }
    \hspace{0.0001\textwidth}
    \subfigure[] {
        \includegraphics[width=0.22\textwidth]{image/Action_4.jpg}
    }
    \caption{展示模式的动画}
\end{figure}

在全景模式下，用户可以由鼠标操作，来查看所有方块的放置情况。

在展示模式下，用户由键盘快捷键和鼠标操作，来按次序查看每个方块。
\begin{itemize}
    \item \textbf{视角切换} 按住鼠标左键进行拖动，即可切换视角。
    \item \textbf{框架切换} 单击鼠标右键，显示或隐藏框架。
    \item \textbf{展示模式} 输入\texttt{g}进入展示模式，输入\texttt{f}退出展示模式。在展示模式下，输入\texttt{n}显示下一个方块，输入\texttt{p}显示上一个方块。
    \item \textbf{退出界面} 输入\texttt{Esc}退出图形化展示界面。
\end{itemize}



\section{项目测试}
\subsection{正确性}
在\texttt{test.cpp}中对于求得的布局方案进行了正确性检验，确保所有立方体没有相交，即解是合法的。并可以通过图形化界面对求得的方案进行了展示，进一步确保求得解的正确性。
\subsection{效率}
项目在\texttt{data}目录中生成了31个测试数据，覆盖了$10-100$个立方体的情况\footnote{由于当方块数较少时，空隙体积较大，无法说明算法效果，故测试数据从10个立方体开始。}，其中立方体的边长为$\in[1,10]$。项目对不同情况下求得解的质量进行了比较，具体测试结果如下：
\begin{table}[h]
\centering
\begin{tabular}{c|c|c||c|c|c}  
 \toprule[1.5pt]
 测试组编号 & 方块个数  &  填充率  & 测试组编号 & 方块个数  &  填充率 \\
\midrule[1pt]
1&	13&	88\%  & 16	&58	&80\% \\ \hline
2&	16&	87\%  & 17	&61	&79\% \\ \hline
3&	19&	85\%  & 18	&64	&78\% \\ \hline
4&	22&	88\%  & 19	&67	&82\% \\ \hline
5&	25&	87\%  & 20	&70	&80\% \\ \hline
6&	28&	93\%  & 21	&73	&76\% \\ \hline
7&	31&	87\%  & 22	&76	&74\% \\ \hline
8&	34&	87\%  & 23	&79	&74\% \\ \hline
9&	37&	87\%  & 24	&82	&73\% \\ \hline
10&	40&	87\%  & 25	&85	&81\% \\ \hline
11&	43&	85\%  & 26	&88	&70\% \\ \hline
12&	46&	91\%  & 27	&91	&74\% \\ \hline
13&	49&	81\%  & 28	&94	&71\% \\ \hline
14&	52&	80\%  & 29	&97	&73\% \\ \hline
15&	55&	79\%  & 30	&100	&71\% \\ 

\bottomrule[1.5pt]
\end{tabular}
\end{table}  

  \begin{figure}[h]
        \centering
        \includegraphics[height=0.35\textwidth]{image/Results.png}
	\caption{Results}
  \end{figure}
其中填充率的计算方式为$\sum $所有方块体积 $/$ 求得包围箱的体积，填充率越大表示方案越优。在测试中，我们选择了算法的快速模式。对于每个测试点，算法在十分钟内进行十次左右的模拟退火过程，返回求得的最优解。所有求得的方案均保存在\texttt{data}目录下。

通过实验结果我们不难看出，在有限时间内解的质量与方块数成负相关关系。在方块数为$10-50$时，填充率基本接近$90\%$；
在方块数为$50-70$时，填充率超过$80\%$；在方块数为$70-100$时，填充率在$75\%$左右。由此可见，尽管解空间是问题规模的阶乘级别的，但算法的效率还是不错的。事实上当运行时间较充裕时，方块数较多的情况也是能得到较不错的解的，如当运行时间为40分钟时，100个方块也能跑出$80\%$以上的填充率。

\begin{thebibliography}{00}
\bibitem {TTREE}{Ping-Hung Yuh, Chia-Lin Yang, Yao-Wen Chang.Temporal Floorplanning Using the T-tree Formulation}
\bibitem {SA}{马少平.人工智能导论课程课件《高级搜索》} 
\end{thebibliography}

\end{document}
